package com.platform.modules.alg.alglib.p924;

public class P924 {
    private final int M = 105;
    // n表示n个皇后
    private int n;
    // x[i]表示第i个皇后放置在第i行第x[i]列
    int x[] = new int[M];
    // countn 表示 n 皇后问题可行解的个数
    long countn;

    public String output = "";

    public String cal(String input) {
        n = Integer.parseInt(input);
        countn = 0;
        Backtrack(1);
        output += countn;
        return output;
    }

    // 判断第 t 个皇后能否放置在第 i 个位置
    boolean Place(int t) {
        boolean ok = true;
        for (int j = 1; j < t; j++)   //判断该位置的皇后是否与前面t-1个已经放置的皇后冲突
        {
            // 判断列、对角线是否冲突
            if (x[t] == x[j] || t - j == Math.abs(x[t] - x[j])) {
                ok = false;
                break;
            }
        }
        return ok;
    }

    void Backtrack(int t) {
        // 如果当前位置为 n,则表示已经找到了问题的一个解
        if (t > n) {
            countn++;
            // 打印选择的路径
            for (int i = 1; i <= n; i++)
                output += x[i] + " ";
            output += "\n";
        } else
            // 分别判断 n 个分支,特别注意 i 不要定义为全局变量,否则递归调用有问题
            for (int i = 1; i <= n; i++) {
                x[t] = i;
                if (Place(t))
                    Backtrack(t + 1); // 如果不冲突的话进行下一行的搜索
            }
    }
}
